using System.Collections.Generic;
using UnityEngine;

namespace SGEngine.ProfilerEx
{
    public class DoubleLinkedListNode
    {
        private static readonly Queue<DoubleLinkedListNode> s_CachedNodes = new Queue<DoubleLinkedListNode>(1024);
        
        public DoubleLinkedListNode Previous;
        public DoubleLinkedListNode next;
        public object Value;
        
        public static DoubleLinkedListNode RequestNode()
        {
            var node = s_CachedNodes.Count > 0 ? s_CachedNodes.Dequeue() : new DoubleLinkedListNode();
            return node;
        }

        public static void ReleaseNode(DoubleLinkedListNode node)
        {
            node.Value = null;
            node.Previous = null;
            node.next = null;
            s_CachedNodes.Enqueue(node);
        }

        public static void ReleaseAllCache()
        {
            s_CachedNodes.Clear();
        }

        private DoubleLinkedListNode() { }

        public void DebugPrint()
        {
            Debug.LogFormat(" [{0}] <- [{1}] -> [{2}]   Cache:[{3}]", Previous != null ? Previous.Value : "NULL",
                Value, next != null ? next.Value : "NULL", s_CachedNodes.Count);
        }
    }
    
    /// <summary>
    /// 双向链表
    /// </summary>
    public class DoubleLinkedList<T> where T : class
    {
        private readonly Dictionary<T, DoubleLinkedListNode> m_Data2NodeMap = new Dictionary<T, DoubleLinkedListNode>(8);
        private DoubleLinkedListNode m_Head;
        private DoubleLinkedListNode m_Last;
        private int m_Count;

        public int Count => m_Count;
        public DoubleLinkedListNode Head => m_Head;
        public DoubleLinkedListNode Last => m_Last;

        public bool Enqueue(T data)
        {
            return AddLast(data);
        }

        public T Dequeue()
        {
            return RemoveHead();
        }

        public T Peek()
        {
            if (m_Head == null)
            {
                return null;
            }
            return (T)m_Head.Value;
        }

        public void Clear()
        {
            m_Count = 0;
            var node = m_Head;
            while (node != null)
            {
                var temp = node;
                node = node.next;
                DoubleLinkedListNode.ReleaseNode(temp);
            }
            
            m_Data2NodeMap.Clear();
            m_Head = m_Last = null;
        }

        /// <summary>
        /// 尾部插入
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        public bool AddLast(T data)
        {
            var node = DoubleLinkedListNode.RequestNode();
            if (!m_Data2NodeMap.TryAdd(data, node))
            {
                Debug.LogErrorFormat("[DoubleLinkedList](AddLast) data:[{0}] Exist !!!", data);
                return false;
            }

            node.Value = data;
            if (m_Count == 0)
            {
                m_Head = m_Last = node;
            }
            else if (m_Count == 1)
            {
                m_Last = node;
                m_Head.next = node;
                m_Last.Previous = m_Head;
            }
            else
            {
                m_Last.next = node;
                node.Previous = m_Last;
                m_Last = node;
            }
            m_Count++;
            
            return true;
        }

        /// <summary>
        /// 头部插入
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        public bool AddHead(T data)
        {
            var node = DoubleLinkedListNode.RequestNode();
            if (!m_Data2NodeMap.TryAdd(data, node))
            {
                Debug.LogErrorFormat("[DoubleLinkedList](AddHead) data:[{0}] Exist !!!", data);
                return false;
            }

            node.Value = data;
            if (m_Count == 0)
            {
                m_Head = m_Last = node;
            }
            else
            {
                node.next = m_Head;
                node.Previous = null;
                m_Head.Previous = node;
                m_Head = node;
            }
            m_Count++;

            return true;
        }

        /// <summary>
        /// 在某个元素后插入
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        public bool AddAfter(T pre, T data)
        {
            if(! m_Data2NodeMap.TryGetValue(pre, out var preNode))
            {
                Debug.LogErrorFormat("[DoubleLinkedList](AddAfter) pre:[{0}] Exist !!!", data);
                return false;
            }
            var node = DoubleLinkedListNode.RequestNode();
            if (!m_Data2NodeMap.TryAdd(data, node))
            {
                Debug.LogErrorFormat("[DoubleLinkedList](AddAfter) data:[{0}] Exist !!!", data);
                return false;
            }

            node.Value = data;
            var oldNext = preNode.next;
            preNode.next = node;
            node.Previous = preNode;
            node.next = oldNext;
            if(oldNext != null)
                oldNext.Previous = node;

            if(preNode == m_Last)
            {
                m_Last = node;
            }
            m_Count++;

            return true;
        }

        public T RemoveHead()
        {
            var head = m_Head;
            if (m_Head == null)
            {
                return null;
            }

            var data = (T)head.Value;
            Remove(data);
            
            return data;
        }
        
        public T RemoveLast()
        {
            var tail = m_Last;
            if (m_Last == null)
            {
                return null;
            }

            var data = (T)tail.Value;
            Remove(data);
            return data;
        }
        
        public bool Remove(T data)
        {
            if (!m_Data2NodeMap.Remove(data, out var node))
            {
                Debug.LogErrorFormat("[DoubleLinkedList](Remove) data:[{0}] Not Exist !!!", data);
                return false;
            }

            if (m_Count == 1)
            {
                m_Head = m_Last = null;
                m_Count = 0;
                DoubleLinkedListNode.ReleaseNode(node);
                return true;
            }

            var previous = node.Previous;
            if (previous == null)
            {//头被移除
                m_Head = m_Head.next;
            }
            else
            {
                previous.next = node.next;
            }

            var next = node.next;
            if (next == null)
            {//尾被移除
                m_Last = m_Last.Previous;
                m_Last.next = null;
            }
            else
            {
                next.Previous = node.Previous;
            }

            m_Count--;
            DoubleLinkedListNode.ReleaseNode(node);

            return true;
        }

        public void DebugPrint()
        {
            Debug.Log("===============================Begin DebugPrint=============================");
            if (m_Count == 0)
            {
                Debug.Log("Empty");
                Debug.Log("===============================End DebugPrint=============================");
                return;
            }

            if (m_Count == 1)
            {
                m_Head.DebugPrint();
                m_Last.DebugPrint();
                Debug.Log("===============================End DebugPrint=============================");
                return;
            }
            
            var begin = m_Head;
            while (begin != null)
            {
                begin.DebugPrint();
                begin = begin.next;
            }
            Debug.Log($"Count:[{m_Count}]]");
            Debug.Log("===============================End DebugPrint=============================");
        }

        //TODO:AddFirst
        //TODO:AddBefore
        //TODO:AddAfter
    }
}